package exp2;

import ch16.LinkedBinaryTree;

import java.util.ArrayList;

/**
 * Created by 春旺 on 2017/10/23.
 */
/*（1）确定树的根节点。树根是当前树中所有元素在先序遍历中最先出现的元素，即先序遍历的第一个结点就是二叉树的跟
（2）求解树的子树。找到根在中序遍历的位置，位置左边就是二叉树的左孩子，位置右边是二叉树的右孩子，如果跟结点左边或右边为空，那么该方向子树为空；如果根节点左边和右边都为空，那么根节点已经为叶子节点。
（3）对二叉树的左、右孩子分别进行步骤（1）（2），直到求出二叉树的结构为止。*/
public class ComeTrueTree<T> {
    private  LinkedBinaryTree root;
    private  LinkedBinaryTree left,right;
    ArrayList <LinkedBinaryTree> node = new ArrayList<>();
        public ArrayList buildTree(Object[] pre, Object[] mid) {

            if (pre.length > 0) {
                T value = (T) pre[0];
              root = new LinkedBinaryTree(value);
                int length = pre.length;
                if (pre.length == 1) {
                    return node;
                }
                int ai = 0;
                while (mid[ai] != value)
                    ai++;


                if (ai >0 && ai < pre.length - 1){
                    left = new LinkedBinaryTree(mid[ai - 1]);
                    right = new LinkedBinaryTree(mid[ai + 1]);
                    node.add(new LinkedBinaryTree(root.getRootElement(), left, right));}
                if (ai>0) {
                    Object[] leftPreOrder = new Object[ai];
                    for (int i = 0; i < leftPreOrder.length; i++) {
                        leftPreOrder[i] = pre[i + 1];
                    }
                    Object[] leftSubMidOrder = new Object[ai];
                    for (int i = 0; i < leftSubMidOrder.length; i++) {
                        leftSubMidOrder[i] = mid[i];
                    }
                    buildTree(leftPreOrder, leftSubMidOrder);
                }
                if(length-ai-1>0) {
                    Object[] rightMidOrder = new Object[length - ai - 1];
                    for (int i = 0; i < rightMidOrder.length; i++) {
                        rightMidOrder[i] = mid[i + ai + 1];
                    }
                    Object[] rightSubPreOrder = new Object[length - ai - 1];

                    for (int i = 0; i < rightSubPreOrder.length; i++) {
                        rightSubPreOrder[i] = pre[i + ai + 1];
                    }
                    buildTree(rightSubPreOrder, rightMidOrder);
                }
                return node;
            }
            else return  null;
        }

    }

